package daily.year2024.m10;

import java.util.*;

/**
 * 前缀树
 *
 * @author wjs 2024/10/3
 */
public class d3 {
    static class Solution1 {
        //前缀树，每一层存储前缀匹配字典序最短的三个单词
        public List<List<String>> suggestedProducts(String[] products, String searchWord) {
            TrieTree root = new TrieTree();
            for(String product : products) {
                addWord(root,product);
            }
            List<List<String>> res = new ArrayList<>();
            char[] chars = searchWord.toCharArray();
            TrieTree cur = root;
            for(int i=0;i < chars.length;i++) {
                int idx = chars[i] -'a';
                List<String> list = new ArrayList<>();
                res.add(list);
                if(cur == null || cur.child[idx] == null) {
                    continue;
                }
                cur = cur.child[idx];
                list.addAll(cur.words);
            }
            return res;
        }

        private void addWord(TrieTree root, String word) {
            char[] chars = word.toCharArray();
            int n = chars.length;
            TrieTree cur = root;
            for(int i=0;i < n;i++) {
                int idx = chars[i] - 'a';
                if(cur.child[idx] == null) {
                    cur.child[idx] = new TrieTree();
                }
                //判断当前节点搜索的前三个结果是否满了，没满要加上，满了要替换
                replaceWords(cur,word);
                cur = cur.child[idx];
            }
            replaceWords(cur,word);
        }
        private void replaceWords(TrieTree cur, String word) {
            if(cur.words.size() < 3) {
                cur.words.add(word);
                Collections.sort(cur.words,(x,y) -> x.compareTo(y));
            } else {
                if(word.compareTo(cur.words.get(2)) < 0) {
                    cur.words.set(2,word);
                    Collections.sort(cur.words,(x,y) -> x.compareTo(y));
                }
            }
        }
    }

    static class TrieTree {
        TrieTree[] child;
        List<String> words;
        public TrieTree() {
            child = new TrieTree[26];
            words = new ArrayList<>();
        }
    }

    static class Solution2 {
        class TrieNode {
            public static final int num = 26;
            TrieNode[] next;
            boolean isEnd;
            PriorityQueue<String> queue;

            public TrieNode() {
                next = new TrieNode[num];
                queue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
            }
        }

        private static final int size = 3;
        private TrieNode root;
        private List<List<String>> ans;

        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new TrieNode();
                }
                node = node.next[c - 'a'];
                node.queue.offer(word);
                if (node.queue.size() > size)
                    node.queue.poll();
            }
            node.isEnd = true;
        }

        public void startWith(String word) {
            TrieNode node = root;
            boolean exist = true;
            for (char c : word.toCharArray()) {
                if (!exist || node.next[c - 'a'] == null) {
                    exist = false;
                    ans.add(new ArrayList<>());
                    continue;
                }
                node = node.next[c - 'a'];
                List<String> tmp = new ArrayList<>();
                while(!node.queue.isEmpty()) {
                    tmp.add(node.queue.poll());
                }
                Collections.reverse(tmp);
                ans.add(tmp);
            }
        }
        public List<List<String>> suggestedProducts(String[] products, String searchWord) {
            ans = new ArrayList<>();
            root = new TrieNode();
            for (String s : products)
                insert(s);
            startWith(searchWord);
            return ans;
        }
    }
}
